package com.kehao.leetcode.jzoffer;

import org.junit.Test;

/**
 * @author Kehao.Chen
 * @version 1.0
 * @date 2022/6/23 20:25
 */
public class JZSolution029 {
    private static class Node {
        public int val;
        public Node next;
        public Node() {}
        public Node(int _val) {
            val = _val;
        }
        public Node(int _val, Node _next) {
            val = _val;
            next = _next;
        }
    };

    public Node insert(Node head, int insertVal) {
        if(head==null){
            Node node = new Node(insertVal);
            node.next = node;
            return node;
        }
        if(head.next==head){
            Node node = new Node(insertVal);
            node.next = head;
            head.next = node;
            return head;
        }
        Node p1 = head,p2 = p1.next;
        while (p1.val<=p2.val){
            if(p1.val<=insertVal&&insertVal<=p2.val){
                p1.next = new Node(insertVal);
                p1.next.next = p2;
                return head;
            }
            p1 = p1.next;
            p2 = p2.next;
            if(p1 ==head){
                break;
            }
        }
        if(p1.val<=insertVal||insertVal<=p2.val){
            p1.next = new Node(insertVal);
            p1.next.next = p2;
            return head;
        }
        p1 = p1.next;
        p2 = p2.next;
        while (p1.val<=p2.val){
            if(p1.val<=insertVal&&insertVal<=p2.val){
                p1.next = new Node(insertVal);
                p1.next.next = p2;
                return head;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return head;
    }

    @Test
    public void test01(){
        int[] arr = {3,3,3};
        Node head = makeNodeList(arr);
        Node insert = insert(head, 2);
        showResult(insert);
    }

    private void showResult(Node head) {
        Node p = head;
        System.out.print(p.val+" ");
        p = p.next;
        while (p!=head){
            System.out.print(p.val+" ");
            p = p.next;
        }
    }

    private Node makeNodeList(int[] arr) {
        if(arr.length==0) return null;
        Node head = new Node();
        Node p = head;
        for (int i = 0; i < arr.length; i++) {
            p.next = new Node(arr[i]);
            p = p.next;
        }
        p.next = head.next;
        return head.next;
    }
}
